/**
 * 搜索二维矩阵 II
 * 题目：编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。
 * 该矩阵具有以下特性：
 * - 每行的元素从左到右升序排列
 * - 每列的元素从上到下升序排列
 * 
 * 算法思路：从右上角开始搜索
 * 1. 从矩阵的右上角（第一行最后一列）开始
 * 2. 如果当前元素等于目标值，返回 true
 * 3. 如果当前元素大于目标值，说明目标值在当前元素的左侧，向左移动（j--）
 * 4. 如果当前元素小于目标值，说明目标值在当前元素的下方，向下移动（i++）
 * 5. 如果越界仍未找到，返回 false
 * 
 * 时间复杂度：O(m + n)，其中 m 是行数，n 是列数
 * 空间复杂度：O(1)
 * 
 * @param matrix - m x n 的二维矩阵，每行从左到右递增，每列从上到下递增
 * @param target - 要搜索的目标值
 * @returns 如果目标值存在于矩阵中，返回 true；否则返回 false
 */
function searchMatrix(matrix: number[][], target: number): boolean {

    const m = matrix.length
    const n = matrix[0].length

    // 从矩阵的右上角开始搜索
    // i 表示当前行，j 表示当前列
    let i = 0
    let j = n - 1

    // 在矩阵范围内进行搜索
    while (i < m && j >= 0) {
        if (target === matrix[i][j]) {
            // 找到目标值
            return true
        } else if (target < matrix[i][j]) {
            // 当前元素大于目标值，目标值在当前元素的左侧
            // 向左移动（列索引减1）
            j--
        } else {
            // 当前元素小于目标值，目标值在当前元素的下方
            // 向下移动（行索引加1）
            i++
        }
    }

    // 搜索完整个矩阵仍未找到目标值
    return false

};